package com.xieyong.leetcode;

import java.util.Arrays;

public class Leetcode2616 {
    public static void main(String[] args) {
        Leetcode2616 leetcode2616 = new Leetcode2616();
        int[] nums = {10,1,2,7,1,3};
        int p = 2;
        int i = leetcode2616.minimizeMax(nums, p);
        System.out.println(i);
    }


    public int minimizeMax(int[] nums, int p) {
        if (p == 0) return 0;
        Arrays.sort(nums);
        int res = 0;
        int left = 0,right = nums[nums.length-1] - nums[0];
        while (left <= right) {
            int mid = left + (right - left) / 2;
            boolean flag = false;
            int count = 0;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] - nums[i - 1] <= mid) {
                    count++;
                    i++;
                    if (count >= p) {
                        flag = true;
                    }
                }
            }
            if (flag) {
                res = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return res;
    }
}
